#include "bst.h"
#include <stdio.h>

static Bst_t* createNode(int item) {
    Bst_t* temp = 
       (Bst_t *)malloc(sizeof(Bst_t));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}


Bst_t* insert(Bst_t *root, int key) {

    if (root==NULL) 
        return createNode(key);
    
    if (root->key == key)
        return root;
    
    if (root->key < key)
        root->right = insert(root->right, key);
    else
        root->left = insert(root->left, key);
    return root;
}

Bst_t* search(Bst_t *root, int key) {
    if (root==NULL || root->key==key)
        return root;
    if (root->key > key)
        return search(root->right, key);
    else
        return search(root->left, key);
}

Bst_t* deleteNode(Bst_t *root, int key) {
    // Base case
    if (root == NULL)
        return root;

    // If key to be searched is in a subtree
    if (root->key > key)
        root->left = deleteNode(root->left, key);
    else if (root->key < key)
        root->right = deleteNode(root->right, key);
    else {
        // If root matches with the given key
        // Cases when root has 0 children 
        // or 
        // only right child
        if (root->left == NULL) {
            Bst_t* temp = root->right;
            free(root);
            return temp;
        }

        // When root has only left child
        if (root->right == NULL) {
            Bst_t* temp = root->left;
            free(root);
            return temp;
        }

        // When both children are present
        Bst_t * succ = rightmost(root);
        root->key = succ->key;
        root->right = deleteNode(root->right, succ->key);
    }
    return root;
}


Bst_t* leftmost(Bst_t *root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}

Bst_t* rightmost(Bst_t *root){
while (root->right != NULL) {
        root = root->right;
    }
    return root;
}

Bst_t* getPred(Bst_t * root, int target) {
    
    Bst_t *targetNode = search(root, target);
    if (targetNode == NULL)
        return NULL;
    Bst_t *pred = leftmost(targetNode);
    return pred;
}

Bst_t* getSucc(Bst_t* root, int target) {
    
    Bst_t * targetNode = search(root, target);
    if (target==NULL)
        return NULL; 
    Bst_t * succ = rightmost(targetNode);
        
    return succ;
}
